Social networking has become one of the dominant ways people gather information and communicate. As the popularity of social networking has grown, social networking sites have attracted have billions of users.
The information generated by or for these users cannot be efficiently stored by a single machine, and as the number of users grows, this information can become spread across thousands of servers. This distribution of information, known as “fan-out,” can cause a single query such as “which users performed action X,” to be executed by each of the thousands of servers, which each may or may not house a part of the requested data. Because queries are distributed, various latencies can be experienced.
Furthermore, for any given page within a social networking site, multiple queries may be executed requiring sophisticated server software to search through vast stores of data to gather information relating to hundreds or even thousands of users. At any given time, millions of these page requests can occur contemporaneously, e.g. when users visit pages, or “timelines” of their friends or other users.
Despite this complexity, the transition from one page to the next within a social networking website appears simple to end users, and unless this page retrieval process occurs with no perceptible delays, users may lose patience and simply navigate to a different website. Therefore, it is desirable to efficiently search for information to reduce website delays caused by query latency and fan-out.